namespace classifier_test
{

namespace high_drift
{

class modularity_clustering : private noncopyable
{
	typedef float weight_type;
public:
	modularity_clustering();
	void clear();
	void set_size(int SetSize);
	void set_division_threshold(double Val);
	void add_edge(int A, int B, double Weight);
	void compute(bool Subdiv);
	int get_cluster_count() const;
	const vector<int>& get_labels() const;
	double get_quality() const;

private:
	struct node
	{
		double EVal, AVal;
		int A, B;
	};
	struct merge
	{
		double Delta;
		int A, B;
	};
	struct merge_worse
	{
		bool operator()(const merge& A, const merge& B) const
		{
			return A.Delta < B.Delta;
		}
	};
	typedef simple_heap<merge, merge_worse> merge_heap;
	typedef simple_graph<pair<weight_type, merge_heap::node*> > merge_graph;

	int Size;
	double DivThreshold;
	simple_graph<weight_type> Graph;
	vector<weight_type> Weights;
	double TotalWeight;
	int NodeCount;
	vector<node> Nodes;
	merge_graph Merges;
	merge_heap Heap;
	int ClusCount;
	vector<int> Labels;
	double Quality;

	void init_nodes();
	void merge_nodes();
	void find_clusters();
	void compute_quality();
	void subdivide();
	double total_weight(int A) const;
	double total_weight() const;
};

}

}

